//
// Created by yanhai on 2021/1/4.
//

// 快速排序
// 思想：分而治之，将一个整体分为两部分，其中一部分均比另一部分的元素小，
//              再分别对这两部分继续排序，已达到整个序列有序的目的。
// 空间复杂度：主要是递归造成的栈空间的使用，
//     最好情况下：每次partition后都平均分成两半  为O(logn)
//     最坏情况下：正序或逆序时，每次划分之后，一个比上一次记录少一个的子序列，另一个为空，
//               如果用递归树画出来，它就是一颗斜树,  为O(n)
//     平均 ：O(logn)


#include <stdio.h>

#define ARRAY_DATA_LENGTH 16

void print(int *data, int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 至少2个元素，只有1个元素不会进到这个函数
// 思路：把最后一个元素作为基准值，从前向后扫描遇到比基准值大的元素 将和 从后向前扫描遇到比基准值小的元素 交换位置
//      从两端向中间扫描完一次整个序列，就停止扫描，并且最后把基准值放在"中间"位置
//      至此，基准值前面的部分都小于等于基准值，基准值后面的部分都大于等于基准值
//      将基准值的位置返回，外层将按照基准值将整个序列分为前后两个部分，两个部分再分别进行同样的排序
int partition(int *data, int start, int end)
{
    int pivot = end;      // 这里取最后一个值作为基准值

    int i = start, j = end - 1;   // i从start向后扫描，j从end前面向前扫描

    do {
        // i从前向后找，找到比基准值大的，就退出循环
        while (i < end && data[i] <= data[pivot])
            i++;

        // j从后面往前找，找到比基准值小的，就退出循环
        while (j > start && data[j] >= data[pivot])
            j--;

        // 将位于前面的比基准值大的数 和 位于后面的比基准值小的数 交换位置
        if (i < j) {
            swap(&data[i], &data[j]);
        }
    } while (i < j);    // 继续两端向中间扫描

    // 因为基准数据选择的是最后一个，因此要和i交换位置，此时i位置要么是一个比基准值大的数，要么就是基准值本身
    // 由于是从小到大排列，所以要将大的数据放到后面去，因此要将i位置的数放到最后，和基准值交换位置
    // j位置要么是一个比基准值小的数，要么是最开头的数
    swap(&data[pivot], &data[i]);
    return i;   // 我们把基准值放在了i位置，返回基准值的位置，所以就是i
}

//(71), 64, 24, 12, 9, 16, 53, 57, 23, 79, 87, 97, 45, 60, 61, 90        key=71
// i                                                       <-- j
// i                                                      j
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 79, 87, 97, 45, 60,(61), 90    data[i] = data[j]
// i -->                                                  j
//                                    i                   j
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 79, 87, 97, 45, 60, 79, 90    data[j] = data[i]
//                                    i               <-- j
//                                    i                j
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 87, 97, 45, 60, 79, 90    data[i] = data[j]
//                                    i -->            j
//                                        i            j
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 87, 97, 45, 87, 79, 90    data[j] = data[i]
//                                        i        <-- j
//                                        i        j
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 45, 97, 45, 87, 79, 90    data[i] = data[j]
//                                        i -->   j
//                                            i   j
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 45, 97, 97, 87, 79, 90    data[j] = data[i]
//                                            i <--j
//                                            i(j)
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 45, 97, 97, 87, 79, 90    data[i] = data[j]
//                                            i-->(j)
//                                            i(j)
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 45, 97, 97, 87, 79, 90    data[j] = data[i]  结束循环
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 45, 71, 97, 87, 79, 90    data[i] = pivotkey
// -----------------------------------------      --------------
//                  ↓                                   ↓
// 61, 64, 24, 12, 9, 16, 53, 57, 23, 60, 45 [71] 97, 87, 79, 90  分成了2组
// -----------------------------------------      --------------

// 思想：取第1个位置作为pivotkey，把值保存下来，此时第1个位置的数据我们认为是多余的了，也可以说成第1个位置被空出来了。
//      先从后向前找，找到比pivotkey小的值x1，把x1的移动到刚才空出来的位置，此时x1对应的位置被空了出来
//      再从前向后找，找到比pivotkey大的值y1，把y1写到之前x1的位置，此时y1位置就被空了出来
//   上面是一个循环，（从两端向中间）只要还没有将数组遍历一遍，那就继续重复上面的步骤
//      再先从后向前找，找到比pivotkey小的值x2，把x2的值写到y1位置，此时x2位置就被空了出来
//      再从前向后找，找到比pivotkey大的值y2，把y2写到之前x2的位置，此时y2位置就被空了出来
//   直到把数组遍历一遍，退出循环，此时yn位置是空的，此时将pivotkey的值放到这个yn的位置
int partition2(int *data, int start, int end)
{
    int i = start, j = end;
    int pivotkey = data[start]; // 取第一个值作为基准值
    while (i < j) {
        // j从后向前找，找到比基准值小的，就退出循环
        while (i < j && data[j] >= pivotkey)
            j--;
        data[i] = data[j];   // 将data[j]这个较小的值放到前面去

        // i从前向后找，找到比基准值大的，就退出循环
        while (i < j && data[i] <= pivotkey)
            i++;
        data[j] = data[i]; // data[i]这个较大的值放到后面去
    }

    // 将key放到"中间"
    // 为什么这里是i位置不是j位置? (虽然i等于j)
    // 可以看到while循环最后是把i位置的值移动到了j位置上面，因此是i位置被空了出来，所以将pivotkey放在i位置上面。
    data[i] = pivotkey;
    return i;
}

// 核心是partition函数
void _quick_sort(int *data, int start, int end)
{
    if (start < end) {
        // 把基准的位置返回，基准左边的数字都小于等于基准，右边的数字都大于等于基准
#if 0
        int pivot = partition(data, start, end);
#else
        int pivot = partition2(data, start, end);
#endif
        _quick_sort(data, start, pivot - 1);    // 对基准左边的元素使用同样的方法排序
        _quick_sort(data, pivot + 1, end);      // 对基准右边的元素使用同样的方法排序
    }
}

// 为了和其他排序方法的参数一致，这里包装一下
void quick_sort(int *data, int length)
{
    _quick_sort(data, 0, length - 1);
}

int main()
{
    int data[ARRAY_DATA_LENGTH] = {71, 64, 24, 12, 9, 16, 53, 57, 23, 79, 87, 97, 45, 60, 61, 90};

    print(data, ARRAY_DATA_LENGTH);
    quick_sort(data, ARRAY_DATA_LENGTH);
    print(data, ARRAY_DATA_LENGTH);

    return 0;
}
